package com.leetcode.code;

import com.leetcode.base.ListNode;

/**
 * 合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
 * <p>
 * 示例:
 * <p>
 * 输入:
 * [
 * 1->4->5,
 * 1->3->4,
 * 2->6
 * ]
 * 输出: 1->1->2->3->4->4->5->6
 */

/**
 * 已发
 */
public class LeetCode0023Java {
    public static void main(String[] args) {
        Solution solution = new Solution();

        ListNode val1 = new ListNode(1);
        val1.next = new ListNode(4);
        val1.next.next = new ListNode(5);

        ListNode val2 = new ListNode(1);
        val2.next = new ListNode(3);
        val2.next.next = new ListNode(4);

        ListNode val3 = new ListNode(2);
        val3.next = new ListNode(6);

        ListNode[] lists = new ListNode[] { val1, val2, val3 };

        System.out.println("结果：" + solution.mergeKLists(lists));
    }

    private static class Solution {
        public ListNode mergeKLists(ListNode[] lists) {

            if (lists.length == 0) {
                return null;
            }
            if (lists.length == 1) {
                return lists[0];
            }
            if (lists.length == 2) {
                return mergeTwoLists(lists[0], lists[1]);
            }

            int mid = lists.length / 2;
            ListNode[] first = new ListNode[mid];
            for (int i = 0; i < mid; i++) {
                first[i] = lists[i];
            }

            ListNode[] second = new ListNode[lists.length - mid];
            for (int i = mid, j = 0; i < lists.length; i++, j++) {
                second[j] = lists[i];
            }

            return mergeTwoLists(mergeKLists(first), mergeKLists(second));
        }

        private ListNode mergeTwoLists(final ListNode first, final ListNode second) {
            if (first == null) {
                return second;
            }
            if (second == null) {
                return first;
            }

            ListNode node = null;

            if (first.val < second.val) {
                node = first;

                if (first.next != null) {
                    node.next = mergeTwoLists(first.next, second);
                } else {
                    node.next = second;
                }
            } else {
                node = second;

                if (second.next != null) {
                    node.next = mergeTwoLists(first, second.next);
                } else {
                    node.next = first;
                }
            }

            return node;
        }
    }
}
